Manual Big-O Analysis
Time: O(n^2) • Space: O(1)
Why: Nested loops detected; suggests quadratic time with constant extra space. These are heuristics; empirical results below provide a practical check.
Time: O(n) • Space: O(n)
Why: Detected recursion without loops and no clear halving pattern. This commonly implies linear recursion depth and O(n) time/space. These are heuristics; empirical results below provide a practical check.
Time: O(n) • Space: O(n)
Why: Detected recursion without loops and no clear halving pattern. This commonly implies linear recursion depth and O(n) time/space. These are heuristics; empirical results below provide a practical check.
Time: O(n^2) • Space: O(1)
Why: Nested loops detected; suggests quadratic time with constant extra space. These are heuristics; empirical results below provide a practical check.
Time: O(n^2) • Space: O(1)
Why: Nested loops detected; suggests quadratic time with constant extra space. These are heuristics; empirical results below provide a practical check.
Beginner & Interview Summaries
When the input size n doubles, the runtime grows by approximately 4.58×, which suggests performance closest to O(n log n).
Interview: knapsack_bruteforce has an estimated time complexity of O(n^2) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.
When the input size n doubles, the runtime grows by approximately 2.67×, which suggests performance closer to O(n).
Interview: knapsack_recursive has an estimated time complexity of O(n) and space complexity of O(n). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.
When the input size n doubles, the runtime grows by approximately 1.58×, which suggests performance closer to O(n).
Interview: knapsack_memo has an estimated time complexity of O(n) and space complexity of O(n). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.
When the input size n doubles, the runtime grows by approximately 1.48×, which suggests performance closer to O(log n).
Interview: knapsack_tab has an estimated time complexity of O(n^2) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.
When the input size n doubles, the runtime grows by approximately 1.41×, which suggests performance closer to O(log n).
Interview: knapsack_1d has an estimated time complexity of O(n^2) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.
Runtime Chart
Runtime Table (mean ± 95% CI)
| n | knapsack_bruteforce | knapsack_recursive | knapsack_memo | knapsack_tab | knapsack_1d |
|---|---|---|---|---|---|
| 5 | 19.40 µs ± 1.50 µs | 9.29 µs ± 2.38 µs | 12.74 µs ± 3.63 µs | 11.64 µs ± 633.67 ns | 8.11 µs ± 1.55 µs |
| 7 | 85.90 µs ± 9.16 µs | 26.26 µs ± 13.91 µs | 23.78 µs ± 14.51 µs | 19.54 µs ± 1.19 µs | 12.11 µs ± 1.04 µs |
| 9 | 393.11 µs ± 33.24 µs | 91.40 µs ± 14.36 µs | 37.25 µs ± 8.18 µs | 31.39 µs ± 2.46 µs | 17.40 µs ± 2.73 µs |
| 11 | 1.84 ms ± 51.26 µs | 171.71 µs ± 143.11 µs | 52.18 µs ± 30.23 µs | 46.97 µs ± 3.03 µs | 28.40 µs ± 13.50 µs |
| 13 | 8.69 ms ± 312.99 µs | 410.46 µs ± 457.26 µs | 92.50 µs ± 53.74 µs | 66.49 µs ± 11.64 µs | 32.88 µs ± 1.69 µs |
| 15 | 38.88 ms ± 1.91 ms | 1.14 ms ± 2.17 ms | 119.83 µs ± 49.96 µs | 78.57 µs ± 1.74 µs | 43.37 µs ± 6.12 µs |
Peak Memory Chart
Memory Table (mean ± 95% CI)
| n | knapsack_bruteforce | knapsack_recursive | knapsack_memo | knapsack_tab | knapsack_1d |
|---|---|---|---|---|---|
| 5 | 208.00 B ± 0.00 B | 130.67 B ± 80.32 B | 1.19 KB ± 1.18 KB | 1.02 KB ± 160.65 B | 408.00 B ± 0.00 B |
| 7 | 225.33 B ± 50.99 B | 206.00 B ± 284.00 B | 2.90 KB ± 2.54 KB | 1.41 KB ± 0.00 B | 486.67 B ± 106.26 B |
| 9 | 257.33 B ± 40.16 B | 130.67 B ± 40.16 B | 5.89 KB ± 5.47 KB | 2.12 KB ± 281.13 B | 658.67 B ± 503.22 B |
| 11 | 304.00 B ± 0.00 B | 158.67 B ± 40.16 B | 6.85 KB ± 250.81 B | 3.33 KB ± 944.43 B | 774.67 B ± 328.73 B |
| 13 | 304.00 B ± 0.00 B | 233.33 B ± 263.36 B | 11.43 KB ± 9.96 KB | 4.28 KB ± 1.00 KB | 1.02 KB ± 240.97 B |
| 15 | 304.00 B ± 0.00 B | 289.33 B ± 200.81 B | 13.77 KB ± 463.16 B | 6.02 KB ± 3.12 KB | 922.67 B ± 281.13 B |
Comparison Summary
Best/worst runtime at each n (lower is better). Mean ranks summarize performance across all n.
| n | Best Runtime | Worst Runtime | Mean Ranks |
|---|---|---|---|
| 5 | knapsack_1d | knapsack_bruteforce | knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00 |
| 7 | knapsack_1d | knapsack_bruteforce | knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00 |
| 9 | knapsack_1d | knapsack_bruteforce | knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00 |
| 11 | knapsack_1d | knapsack_bruteforce | knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00 |
| 13 | knapsack_1d | knapsack_bruteforce | knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00 |
| 15 | knapsack_1d | knapsack_bruteforce | knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00 |
Mean Runtime Comparison (bar)
Bar chart placeholder: you can render an additional Plotly bar chart here comparing means per function.
Methods & Notes
- Runtime measured with
time.perf_counter(); each (function, n) pair ran 3 times after 2 warmup iterations. GC was enabled and collected before runs. - Memory peak measured with
tracemallocbackend (tracemallocby default). - Confidence Intervals: T at 95% confidence. T-intervals use standard t critical values; bootstrap uses 2,000 resamples with a fixed seed.
- Reference curves (O(1), O(log n), O(n), O(n log n), plus any custom) were normalized at the largest n to match the average observed runtime scale.